package 滑动窗口And双指针;

import java.util.HashMap;
import java.util.Map;

public class leetcode3无重复的最长字串 {

    /*
       这个题 的 特殊点就是可以使用 map 来优化
       left 的 向右 扩的 一个 过程
       ，一般的  滑动窗口 都是  使用
       while（） 来使 left 向 右扩到一个 新的 **临界点**
     */


    // 0 <= s.length <= 5 * 104
    // O(N ^ 2) ,居然过了 !
    public int solution(String s){
        int ans  = 0;
        for(int i = 0;i < s.length();i++){
            Map<Character,Integer> map = new HashMap<>();
            int temp = 0;
            for(int j = i;j < s.length();j++){
                if(map.containsKey(s.charAt(j))){
                    break;
                }
                map.put(s.charAt(j),1);
                temp++;
            }
            ans = Math.max(ans,temp);
        }
        return ans;
    }

    /*
    滑动窗口: 这个 比 O(N ^ 2) 的 优化的点在哪里
    举个例子:
    a b c d e f g h d .........
    ^ |   |
      ^   |
          ^
    ^ left 左边界的 移动!
    能不能  在 O(1) 的时间 求出 d 出现过的 位置, 显然 是 可以的嘛
    map 呗!
    这个 map 是 哈希 map 或者 自己的  数组 [] map 都可以
     */
    public static int solutionSlide(String s){
        int ans = 0;
        int left = 0; // left 当前窗口的 左边界  i 是当前窗口的 有边界
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0;i < s.length();i++){
            if(map.containsKey(s.charAt(i))){
                /*
                 这一点 是 很核心的 , 如果 s[i] 出现 在 left 左边界 之前, 那就不用管,left 不变
                 如果 s[i] 在 left ~ i (这就是维护的窗口) 内出现, 那么 需要 更新 窗口的 left
                 为 s[i]  的下一个位置!
                 */
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            ans = Math.max(ans,i - left + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(solutionSlide(s));
    }

    /*
     还挺牛!
     */
    public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }
        return res;
    }
}
